|
Blotto games (or Colonel Blotto games, or "Divide a Dollar" games) constitute a class of two-person zero-sum games in which the players are tasked to simultaneously distribute limited resources over several objects (or battlefields). In the classic version of the game, the player devoting the most resources to a battlefield wins that battlefield, and the gain (or payoff) is then equal to the total number of battlefields won. The Colonel Blotto game was first proposed and solved by Émile Borel〔(The Theory of Play and Integral Equations with Skew Symmetric Kernels ) (1953 translation from the French paper "(La théorie du jeu et les équations intégrales à noyau symétrique gauche )")〕 in 1921, as an example of a game in which "the psychology of the players matters". It was studied after the Second World War by scholars in Operation Research, and became a classic in Game Theory.〔Guillermo Owen, Game Theory, Academic Press (1968)〕 The game is named after the fictional Colonel Blotto from Gross and Wagner's 1950〔(A Continuous Colonel Blotto Game )〕 paper. The Colonel was tasked with finding the optimum distribution of his soldiers over N battlefields knowing that: # on each battlefield the party that has allocated the most soldiers will win, but # both parties do not know how many soldiers the opposing party will allocate to each battlefield, and: # both parties seek to maximize the number of battlefields they expect to win. ==Example== As an example Blotto game, consider the game in which two players each write down three positive integers in non-decreasing order and such that they add up to a pre-specified number S. Subsequently, the two players show each other their writings, and compare corresponding numbers. The player who has two numbers higher than the corresponding ones of the opponent wins the game. For S = 6 only three choices of numbers are possible: (2, 2, 2), (1, 2, 3) and (1, 1, 4). It is easy to see that: :Any triplet against itself is a draw :(1, 1, 4) against (1, 2, 3) is a draw :(1, 2, 3) against (2, 2, 2) is a draw :(2, 2, 2) beats (1, 1, 4) It follows that the optimum strategy is (2, 2, 2) as it does not do worse than breaking even against any other strategy while beating one other strategy. There are however several Nash equilibria. If both players choose the strategy (2, 2, 2) or (1, 2, 3), then none of them can beat the other one by changing strategies, so every such strategy pair is a Nash equilibrium. For larger S the game becomes progressively more difficult to analyze. For S = 12, it can be shown that (2, 4, 6) represents the optimal strategy, while for S > 12, deterministic strategies fail to be optimal. For S = 13, choosing (3, 5, 5), (3, 3, 7) and (1, 5, 7) with probability 1/3 each can be shown to be the optimal probabilistic strategy. Borel's game is similar to the above example for very large S, but the players are not limited to round integers. They thus have an infinite number of available pure strategies, indeed a continuum. This concept is also implemented in a story of Sun Tzu when watching a chariot race with three different races running concurrently. In the races each party had the option to have one chariot team in each race, and each chose to use a strategy of 1, 2, 3 (with 3 being the fastest chariot and 1 being the slowest) to deploy their chariots between the three races creating close wins in each race and few sure outcomes on the winners. When asked how to win Sun Tzu advised the chariot owner to change his deployment to that of 2, 3, 1. Though he would be sure to lose the race against the fastest chariots (the 3 chariots); he would win each of the other races, with his 3 chariot easily beating 2 chariots and his 2 chariot beating the 1 chariots. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Blotto games」の詳細全文を読む スポンサード リンク
|